import java.util.*;

public class Myshu {
    class Shu
    {
        int val;
        Shu left;
        Shu right;

        public Shu(int val) {
            this.val = val;
        }
    }
    public  Shu creat()
    {
        Shu a=new Shu(3);
        Shu b=new Shu(5);
        Shu c=new Shu(1);
        Shu d=new Shu(6);
        Shu f=new Shu(2);
        Shu g=new Shu(0);
        Shu z=new Shu(8);
        Shu h=new Shu(7);
        Shu m=new Shu(4);
        a.left=b;
        a.right=c;
        b.left=d;
        b.right=f;
        c.left=g;
        c.right=z;
        f.left=h;
        f.right=m;

        return a;


    }
    public int getLeaf(Shu root)
    {
       if(root==null)
       {
           return 0;
       }
        if(root.left==null&&root.right==null)
        {
            return 1;
        }
        return getLeaf(root.left)+getLeaf(root.right);
    }
    public int size1(Shu root)
    {
        if(root==null)
        {
            return 0;
        }
        return size1(root.left)+size1(root.right)+1;
    }
    public  void predisplay(Shu n)
    {
        if(n==null)
        {
           return;
        }
        System.out.print(n.val+"");
        predisplay(n.left);
        predisplay(n.right);
        //return

    }
    public void middisplay(Shu n)
    {
        if(n==null)
        {
            return;
        }
        middisplay(n.left);
        System.out.print(n.val+"");
        middisplay(n.right);
    }
    public void houdisplay(Shu n)
    {
        if(n==null)
        {
            return;
        }
        houdisplay(n.left);
        houdisplay(n.right);
        System.out.print(n.val+"");
    }
    public int size(Shu n)
    {
        if(n==null)
        {
            return 0;
        }
        else {
            return size(n.left) + size(n.right) + 1;
        }
    }
    public int getLeafNodeCount(Shu n)
    {
        if(n==null)
        {
            return 0;
        }
        if(n.left==null&&n.right==null)
        {
            return 1;
        }
        else
        {
            return getLeafNodeCount(n.left)+getLeafNodeCount(n.right);
        }
    }
    public int getKLeveInode(Shu n,int k)
    {
        if(n==null||k<=0)
        {
            return 0;
        }
        if(k==1)
        {
            return 1;
        }
        else
        {
            return getKLeveInode(n.left,k-1)+getKLeveInode(n.right,k-1);
        }


    }

    public int getHeight(Shu root)
    {
        if(root==null)
        {
            return 0;
        }
        int a=getHeight(root.left);
        int b=getHeight(root.right);
        return a>b?a+1:b+1;

    }
    public boolean find(Shu root,int a)
    {
        if(root==null)
        {
            return false;
        }
        if(root.val==a)
        {
            return true;
        }

        if(find(root.left,a))
        {
            return true;
        }
        if(find(root.right,a))
        {
            return true;
        }
        return false;

    }


   public List<List<Integer>> levelOrder(Shu root) {
        List<List<Integer>> a=new ArrayList<>();
        Queue<Shu>c=new LinkedList<>();
        c.offer(root);
        while(!c.isEmpty())
        {
            List<Integer>f=new ArrayList<>();
            int sz=c.size();
            while(sz>0)
            {
               Shu b=c.poll();
                f.add(b.val);
                if(b.left!=null)
                {
                    c.offer(b.left);

                }
                if(b.right!=null)
                {
                    c.offer(b.right);
                }


            }
            a.add(f);




        }
        return a;

    }


    public void fenceng(Shu a)
    {
        //List<List<Shu>> n=new ArrayList<>();

        Queue<Shu> b=new LinkedList<>();
        b.offer(a);
        //int i=0;

        while(!b.isEmpty())
        {
            int f= b.size();
            List<Shu> tmp=new ArrayList<>();
            while(f>0) {
                //List<Shu> tmp=new ArrayList<>();


                Shu c = b.poll();
                tmp.add(c);
                System.out.print(c.val + "");

               if(c.left!=null)
               {
                    b.offer(c.left);
                }
                if (c.right != null) {
                    b.offer(c.right);
                }
                f--;
            }
            //n.add(tmp);



        }

    }
    public boolean panduan(Shu a) {
        //List<List<Shu>> n=new ArrayList<>();
        if(a==null)
        {
            return true;
        }

        Queue<Shu> b = new LinkedList<>();
        b.offer(a);
        //int i=0;

        while (!b.isEmpty()) {
            //int f= b.size();
            //List<Shu> tmp=new ArrayList<>();

            //List<Shu> tmp=new ArrayList<>();


            Shu c = b.poll();
            if (c == null) {
                break;
            }
            //tmp.add(c);
            //System.out.print(c.val + "");


            b.offer(c.left);


            b.offer(c.right);
        }

        while (!b.isEmpty()) {

            Shu c = b.poll();
            if (c != null) {
                return false;
            }
        }
        return true;
    }









    public Shu lowestCommonAncestor(Shu root, Shu p, Shu q) {
        if(root==null||p==null||q==null)
        {
            return null;
        }
        Stack<Shu> b=new Stack<>();

            int sz1=b.size();

        Stack<Shu>c=new Stack<>();

            int sz2=c.size();

        int sz=sz1-sz2;
        if(sz>0)
        {
            sz=sz2-sz1;
            Stack<Shu>d=b;
            b=c;
            c=d;

        }
        while(sz>0)
        {
            b.pop();
            sz--;
        }
        while(!b.empty()&&!c.empty())
        {
            Shu g=b.pop();
            Shu l=c.pop();
            if(g==l)
            {
                return g;
            }

        }
        return null;





    }
    public boolean zhaolian(Shu root,Shu p,Stack<Shu>a)
    {
        if(root==null||p==null)
        {
            return false;
        }
        a.push(root);
        if(root==p)
        {
            return true;
        }
        boolean c=zhaolian(root.left,p,a);
        if(c==true)
        {
            return true;
        }
        boolean d=zhaolian(root.right,p,a);
        if(d==true)
        {
            return true;
        }
        a.pop();
        return false;







        /*public List<Integer> preorderTraversal(Shu root) {
        List<Integer>a=new ArrayList<>();
       Stack<Shu>b=new Stack<>();


       Shu cur=root;
        Shu top=null;
        b.push(cur);
        a.add(cur.val);
        cur=cur.left;

        while(!b.empty())
        {



            if(cur!=null)
            {
                b.push(cur);
                a.add(cur.val);
                //cur=cur.left;
            }
            else
            {
                top=b.pop();
                cur=top.right;
                if(cur!=null)
                {
                    b.push(cur);
                    a.add(cur.val);
                }
                else
                {
                    top=b.pop();
                }


            }



        }
        return a;

    }
    public Shu find(Shu root,int val)
    {
        if(root==null)
        {
            return null;
        }
        if(root.val==val)
        {
            return root;
        }
        Shu a=find(root.left,val);
        if(a!=null)
        {
            return a;
        }
        Shu b=find(root.right,val);
        if(b!=null)
        {
            return b;
        }
        return null;



    }

    boolean isSymmetrical1(Shu pRoot) {
        if(pRoot==null)
        {
            return true;
        }
        if(pRoot.left==null&&pRoot.right==null)
        {
            return true;
        }
        if(pRoot.left==null&&pRoot.right!=null||pRoot.left!=null&&pRoot.right==null)
        {
            return false;
        }
        if(pRoot.left.val!=pRoot.right.val)
        {
            return false;
        }
        if(!isdui(pRoot.left,pRoot.right))
        {
            return false;

        }
        return true;




    }
    public boolean isdui(Shu root1,Shu root2)
    {
        if(root1.left==null&&root1.right==null&&root2.left==null&&root2.right==null)
        {
            return true;
        }
        if(root1.left==null&&root2.right!=null||root1.left!=null&&root2.right==null)
        {
            return false;
        }
        if(root1.right==null&&root2.left!=null||root1.right!=null&&root2.left==null)
        {
            return false;
        }
        if(root1.left.val!=root2.right.val||root1.right.val!=root2.left.val)
        {
            return false;
        }
        if(!isdui(root1.left,root1.right))
        {
            return false;
        }
        return true;
    }
    public Shu lowestCommonAncestor(Shu root, Shu p, Shu q) {
        if(p==null||q==null)
        {
            return null;
        }
        Stack<Shu>a=new Stack<>();
        Stack<Shu>b=new Stack<>();
        int sz1=0;
        int sz2=0;
        if(find(root,p,a))
        {
            sz1=a.size();
        }
        if(find(root,q,a))
        {
            sz2=a.size();
        }
        int sz=0;
        if(sz1>sz2)
        {
            sz=sz1-sz2;
            while(sz!=0)
            {
                a.pop();
                sz--;
            }


        }
        else
        {
            sz=sz2-sz1;
            while(sz!=0)
            {
                b.pop();
                sz--;
            }

        }
        while(!a.empty())
        {
            Shu cur1=a.pop();
            Shu cur2=b.pop();
            if(cur1==cur2)
            {
                return cur1;
            }
        }
        return null;
    }



    public boolean find(Shu root,Shu p,Stack<Shu>a)
    {
        if(root==null)
        {
            return false;
        }
        a.push(root);
        if(root==p)
        {
            return true;
        }
        if(root.left==null&&root.right==null)
        {
            a.pop();
        }
        if(find(root.left,p,a))
        {
            return true;
        }
        if(find(root.right,p,a))
        {
            return true;
        }
        return false;





    }

         */

}
























/*class text {
    /*public static void main(String[] args) {
        Myshu v = new Myshu();
        Myshu.Shu z = v.creat();
        Myshu.Shu c=v.lowestCommonAncestor(z,Myshu.Shu b,Myshu.shu c );

        /*v.predisplay(b);
        System.out.println();
        v.middisplay(b);
        System.out.println();
        v.houdisplay(b);
        System.out.println();
        //int c = v.size(b);
        //System.out.println(c);
        //int d = v.getLeafNodeCount(b);
        // System.out.println(d);
        //int f = v.getKLeveInode(b, 3);
        //System.out.println(f);
        //int z = v.getHeight(b);
        //System.out.println(z);
        //System.out.println(v.find(b,9));
        //v.fenceng(b);
        //System.out.println(v.panduan(b));
        //v.preorderTraversal(b);
        int c=v.size1(b);
        System.out.println(c);
        int d=v.getLeaf(b);
        System.out.println(d);
        Myshu.Shu a=v.find(b,5);
        boolean l=v.isSymmetrical1(b);
        System.out.println(l);
       // System.out.println(a.val);






    //}
}



